package com.example.demo;

import org.junit.jupiter.api.Test;

public class FindMedianSortedArray {

    /**
     * Median of Two Sorted Arrays
     * 数组个数为奇数，取中间那个数
     * 数组个数为偶数，取中间两个数的平均值
     * 把两个有序数组合并为一个有序数组可以参考本题
     */
    @Test
    public void findMedianSortedArrayTest() {

    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;

        if (n1 == 0) {
            if (n2 % 2 == 0) {
                return (nums2[n2 / 2 - 1] + nums2[n2 / 2]) / 2.0;
            } else {
                return nums2[n2 / 2];
            }
        }

        if (n2 == 0) {
            if (n1 % 2 == 0) {
                return (nums1[n1 / 2 - 1] + nums1[n1 / 2]) / 2.0;
            } else {
                return nums1[n1 / 2];
            }
        }

        int count = 0;
        int i1 = 0, i2 = 0;
        int[] nums = new int[n1 + n2];

        while (count != (n1 + n2)) {
            if (i1 == n1) {
                while (i2 < n2) {
                    nums[count++] = nums2[i2++];
                }
                break;
            }

            if (i2 == n2) {
                while (i1 < n1) {
                    nums[count++] = nums2[i1++];
                }
                break;
            }

            if (nums1[i1] < nums2[i2]) {
                nums[count++] = nums1[i1++];
            } else {
                nums[count++] = nums2[i2++];
            }
        }

        if (count % 2 == 0) {
            return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
        } else {
            return nums[count / 2];
        }
    }
}
